<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>二叉树遍历</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="二叉树遍历">二叉树遍历</h1>
<pre><code class="language-python"><div><span class="hljs-comment"># coding:utf-8</span>

<span class="hljs-keyword">import</span> click

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span><span class="hljs-params">(object)</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, val)</span>:</span>
        self.left = <span class="hljs-literal">None</span>
        self.right = <span class="hljs-literal">None</span>
        self.val = val

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">print_name</span><span class="hljs-params">(f)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__f</span><span class="hljs-params">(*args, **argk)</span>:</span>
        print(f.__name__)
        <span class="hljs-keyword">return</span> f(*args, **argk)
    <span class="hljs-keyword">return</span> __f


<span class="hljs-comment"># interactive</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert_node</span><span class="hljs-params">(node, val)</span>:</span>
    <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
        <span class="hljs-keyword">return</span> Node(val)
    <span class="hljs-keyword">if</span> val &lt;= node.val:
        node.left = insert_node(node.left, val)
    <span class="hljs-keyword">else</span>:
        node.right = insert_node(node.right, val)
    <span class="hljs-keyword">return</span> node

vals = [<span class="hljs-number">6</span>, <span class="hljs-number">4</span>, <span class="hljs-number">7</span>, <span class="hljs-number">3</span>, <span class="hljs-number">9</span>, <span class="hljs-number">8</span>, <span class="hljs-number">1</span>, <span class="hljs-number">5</span>, <span class="hljs-number">2</span>]

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">create_tree</span><span class="hljs-params">(vals)</span>:</span>
    root = insert_node(<span class="hljs-literal">None</span>, vals[<span class="hljs-number">0</span>])
    <span class="hljs-keyword">for</span> val <span class="hljs-keyword">in</span> vals[<span class="hljs-number">1</span>:]:
        insert_node(root, val)
    <span class="hljs-keyword">return</span> root

root = create_tree(vals)


<span class="hljs-comment"># recursive</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert_node2</span><span class="hljs-params">(node, val)</span>:</span>
    <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
        <span class="hljs-keyword">return</span> Node(val)
    pre = <span class="hljs-literal">None</span>
    cur = node
    <span class="hljs-keyword">while</span> cur:
        pre = cur
        <span class="hljs-keyword">if</span> val &lt;= cur.val:
            cur = cur.left
        <span class="hljs-keyword">else</span>:
            cur = cur.right
    <span class="hljs-keyword">if</span> val &lt;= pre.val:
        pre.left = Node(val)
    <span class="hljs-keyword">else</span>:
        pre.right = Node(val)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">create_tree2</span><span class="hljs-params">(vals)</span>:</span>
    root = insert_node2(<span class="hljs-literal">None</span>, vals[<span class="hljs-number">0</span>])
    <span class="hljs-keyword">for</span> val <span class="hljs-keyword">in</span> vals[<span class="hljs-number">1</span>:]:
        insert_node2(root, val)
    <span class="hljs-keyword">return</span> root

root2 = create_tree2(vals)


<span class="hljs-comment">###################################################</span>
<span class="hljs-comment"># (1) pre</span>
<span class="hljs-comment">###################################################</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pre_order_travel</span><span class="hljs-params">(node, level=<span class="hljs-number">0</span>)</span>:</span>
    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
        <span class="hljs-keyword">return</span>
    ident = <span class="hljs-string">"  "</span> * level
    print(<span class="hljs-string">f"<span class="hljs-subst">{ident}</span><span class="hljs-subst">{node.val}</span>"</span>)
    pre_order_travel(node.left, level+<span class="hljs-number">1</span>)
    pre_order_travel(node.right, level+<span class="hljs-number">1</span>)



<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pre_order_travel2</span><span class="hljs-params">(node, level=<span class="hljs-number">0</span>)</span>:</span>
    visited = {}
    stack = [node]
    <span class="hljs-keyword">while</span> stack:
        node = stack.pop()
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
            <span class="hljs-keyword">continue</span>
        <span class="hljs-keyword">if</span> node <span class="hljs-keyword">in</span> visited:
            print(node.val)
        <span class="hljs-keyword">else</span>:
            stack.append(node.right)
            stack.append(node.left)
            stack.append(node)
            visited[node] = <span class="hljs-literal">True</span>


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pre_order_morris</span><span class="hljs-params">(node)</span>:</span>
    current = node
    <span class="hljs-keyword">while</span> current:
        <span class="hljs-keyword">if</span> current.left == <span class="hljs-literal">None</span>:
            print(current.val)
            current = current.right
        <span class="hljs-keyword">else</span>:
            temp = current.left
            <span class="hljs-keyword">while</span> temp.right != <span class="hljs-literal">None</span> <span class="hljs-keyword">and</span> temp.right != current:
                temp = temp.right
            <span class="hljs-keyword">if</span> temp.right == <span class="hljs-literal">None</span>:
                <span class="hljs-comment"># the first time</span>
                print(current.val)
                temp.right = current
                current = current.left
            <span class="hljs-keyword">else</span>:
                temp.right = <span class="hljs-literal">None</span>
                current = current.right

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">inorder</span><span class="hljs-params">(r: TreeNode)</span>:</span>
    <span class="hljs-keyword">return</span> inorder(r.left) + [r.val] + inorder(r.right) <span class="hljs-keyword">if</span> r <span class="hljs-keyword">else</span> []

<span class="hljs-comment">###################################################</span>
<span class="hljs-comment"># (2) middle</span>
<span class="hljs-comment">###################################################</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">middle_order_travel</span><span class="hljs-params">(node, level=<span class="hljs-number">0</span>)</span>:</span>
    <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
        <span class="hljs-keyword">return</span>
    middle_order_travel(node.left,  level+<span class="hljs-number">1</span>)
    ident = <span class="hljs-string">"  "</span> * level
    print(<span class="hljs-string">f"<span class="hljs-subst">{ident}</span><span class="hljs-subst">{node.val}</span>"</span>)
    middle_order_travel(node.right,  level+<span class="hljs-number">1</span>)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">middle_order_travel2</span><span class="hljs-params">(node)</span>:</span>
    visited = {}
    stack = [node]
    <span class="hljs-keyword">while</span> stack:
        node = stack.pop()
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
            <span class="hljs-keyword">continue</span>
        <span class="hljs-keyword">if</span> node <span class="hljs-keyword">in</span> visited:
            print(node.val)
        <span class="hljs-keyword">else</span>:
            stack.append(node.right)
            stack.append(node)
            stack.append(node.left)
            visited[node] = <span class="hljs-literal">True</span>


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">middle_order_morris</span><span class="hljs-params">(node)</span>:</span>
    current = node
    <span class="hljs-keyword">while</span> current:
        <span class="hljs-keyword">if</span> current.left == <span class="hljs-literal">None</span>:
            print(current.val)
            current = current.right
        <span class="hljs-keyword">else</span>:
            temp = current.left
            <span class="hljs-keyword">while</span> temp.right != <span class="hljs-literal">None</span> <span class="hljs-keyword">and</span> temp.right != current:
                temp = temp.right
            <span class="hljs-keyword">if</span> temp.right == <span class="hljs-literal">None</span>:
                temp.right = current
                current = current.left
            <span class="hljs-keyword">else</span>:
                print(current.val)
                temp.right = <span class="hljs-literal">None</span>
                current = current.right


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">middle_order_travel3</span><span class="hljs-params">(node)</span>:</span>
    stack = []
    current = node
    <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
        <span class="hljs-keyword">while</span> current:
            stack.append(current)
            current = current.left
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> stack:
            <span class="hljs-keyword">break</span>
        current = stack.pop()
        print(current.val)
        current = current.right


<span class="hljs-comment">###################################################</span>
<span class="hljs-comment"># (3) post</span>
<span class="hljs-comment">###################################################</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">post_order_travel</span><span class="hljs-params">(node, level=<span class="hljs-number">0</span>)</span>:</span>
    <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
        <span class="hljs-keyword">return</span>
    post_order_travel(node.left, level+<span class="hljs-number">1</span>)
    post_order_travel(node.right, level+<span class="hljs-number">1</span>)
    ident = <span class="hljs-string">"  "</span> * level
    print(<span class="hljs-string">f"<span class="hljs-subst">{ident}</span><span class="hljs-subst">{node.val}</span>"</span>)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">post_order_travel2</span><span class="hljs-params">(node)</span>:</span>
    visited = {}
    stack = [node]
    <span class="hljs-keyword">while</span> stack:
        node = stack.pop()
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
            <span class="hljs-keyword">continue</span>
        <span class="hljs-keyword">if</span> node <span class="hljs-keyword">in</span> visited:
            print(node.val)
        <span class="hljs-keyword">else</span>:
            stack.append(node)
            stack.append(node.right)
            stack.append(node.left)
            visited[node] = <span class="hljs-literal">True</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">post_order_travel3</span><span class="hljs-params">(node)</span>:</span>
    stack = [node]
    result = []
    <span class="hljs-keyword">while</span> stack:
        node = stack.pop()
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
            <span class="hljs-keyword">continue</span>
        result.append(node.val)
        stack.append(node.left)
        stack.append(node.right)
    print(result[::<span class="hljs-number">-1</span>])

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">post_oder_morris</span><span class="hljs-params">(root)</span>:</span>
    cur = root
    <span class="hljs-keyword">while</span> cur:
        <span class="hljs-keyword">if</span> cur.left == <span class="hljs-literal">None</span>:
            cur = cur.right
        <span class="hljs-keyword">else</span>:
            tmp = cur.left
            <span class="hljs-keyword">while</span> tmp.right != <span class="hljs-literal">None</span> <span class="hljs-keyword">and</span> tmp.right != cur:
                tmp = tmp.right
            <span class="hljs-keyword">if</span> tmp.right == <span class="hljs-literal">None</span>:
                tmp.right = cur
                cur = cur.left
            <span class="hljs-keyword">else</span>:
                tmp.right = <span class="hljs-literal">None</span>
                reverse_print(cur.left)
                cur = cur.right

    reverse_print(root)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverse_print</span><span class="hljs-params">(node1)</span>:</span>
    vals = []
    cur = node1
    <span class="hljs-keyword">while</span> cur:
        vals.append(cur.val)
        cur = cur.right
    print(vals[::<span class="hljs-number">-1</span>])

<span class="hljs-comment">#################################</span>
<span class="hljs-comment"># (4) del node</span>
<span class="hljs-comment">#################################</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">del_node</span><span class="hljs-params">(node, val)</span>:</span>
    <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
    <span class="hljs-keyword">if</span> node.val == val:
        <span class="hljs-keyword">if</span> node.left == <span class="hljs-literal">None</span> <span class="hljs-keyword">and</span> node.right == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
        <span class="hljs-keyword">elif</span> node.left == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> node.right
        <span class="hljs-keyword">elif</span> node.right == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> node.left
        <span class="hljs-keyword">else</span>:
            tmp = node.right
            <span class="hljs-keyword">while</span> tmp.left:
                tmp = tmp.left
            node.val = tmp.val
            node.right = del_node(node.right, tmp.val)
    <span class="hljs-keyword">elif</span> val &lt; node.val:
        node.left = del_node(node.left, val)
    <span class="hljs-keyword">else</span>:
        node.right = del_node(node.right, val)
    <span class="hljs-keyword">return</span> node

<span class="hljs-comment">#####################################</span>
<span class="hljs-comment"># (5) layer travel</span>
<span class="hljs-comment">#####################################</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">layer_travel</span><span class="hljs-params">(root)</span>:</span>
    stack = [root]
    <span class="hljs-keyword">while</span> stack:
        stack2 = []
        <span class="hljs-keyword">while</span> stack:
            node = stack.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
                <span class="hljs-keyword">continue</span>
            stack2.append(node.left)
            stack2.append(node.right)
            print(node.val, end=<span class="hljs-string">" "</span>)
        stack = stack2
        print(<span class="hljs-string">""</span>)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">layer_travel2</span><span class="hljs-params">(root)</span>:</span>
    stack = [root]
    <span class="hljs-keyword">while</span> stack:
        node = stack.pop(<span class="hljs-number">0</span>)
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node:
            <span class="hljs-keyword">continue</span>
        stack.append(node.left)
        stack.append(node.right)
        print(node.val, end=<span class="hljs-string">" "</span>)
    print(<span class="hljs-string">""</span>)

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">layer_travel3</span><span class="hljs-params">(root)</span>:</span>
    stack = [root]
    num = <span class="hljs-number">1</span>
    <span class="hljs-keyword">while</span> stack:
        num2 = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(num):
            node = stack.pop(<span class="hljs-number">0</span>)
            print(node.val, end=<span class="hljs-string">" "</span>)
            <span class="hljs-keyword">if</span> node.left:
                stack.append(node.left)
                num2 += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> node.right:
                stack.append(node.right)
                num2 += <span class="hljs-number">1</span>
        print(<span class="hljs-string">""</span>)
        num = num2
    




<span class="hljs-meta">@click.group()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>:</span>
    <span class="hljs-keyword">pass</span>

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"insert_node"</span>)
    pre_order_travel(root)
    print(<span class="hljs-string">"insert_node2"</span>)
    pre_order_travel(root2)

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pre</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"pre_order_travel"</span>)
    pre_order_travel(root)
    print(<span class="hljs-string">"pre_order_travel2"</span>)
    pre_order_travel2(root)
    print(<span class="hljs-string">"pre_order_morris"</span>)
    pre_order_morris(root)

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">middle</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"middle_order_travel"</span>)
    middle_order_travel(root)
    print(<span class="hljs-string">"middle_order_travel2"</span>)
    middle_order_travel2(root)
    print(<span class="hljs-string">"middle_order_morris"</span>)
    middle_order_morris(root)
    print(<span class="hljs-string">"middle_order_travel3"</span>)
    middle_order_travel3(root)

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">post</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"post_order_travel"</span>)
    post_order_travel(root)
    print(<span class="hljs-string">"post_order_travel2"</span>)
    post_order_travel2(root)
    print(<span class="hljs-string">"post_order_travel3"</span>)
    post_order_travel3(root)
    print(<span class="hljs-string">"post_oder_morris"</span>)
    post_oder_morris(root)

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">delnode</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"middle_order_travel"</span>)
    middle_order_travel(root)
    print(<span class="hljs-string">"del_node 4"</span>)
    del_node(root, <span class="hljs-number">4</span>)    
    print(<span class="hljs-string">"middle_order_travel"</span>)
    middle_order_travel(root)

<span class="hljs-meta">@main.command()</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">layer</span><span class="hljs-params">()</span>:</span>
    print(<span class="hljs-string">"layer_travel"</span>)
    layer_travel(root)
    print(<span class="hljs-string">"layer_travel2"</span>)
    layer_travel2(root)    
    print(<span class="hljs-string">"layer_travel3"</span>)
    layer_travel3(root)

<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">'__main__'</span>:
    main()



</div></code></pre>

    </body>
    </html>